package BinaryTree;

import java.util.HashMap;
import java.util.HashSet;

/**
 * 求一个二叉树的两个节点向上会聚的第一个点
 * 类比家谱就是最近的公共祖先节点
 *
 * @author Liaorun
 */
public class LowestCommonAncestor {
    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int value) {
            this.value = value;
        }
    }


    /**
     * 前提：两个节点属于 head为头的二叉树
     * 求一个二叉树的两个节点向上会聚的第一个点
     *
     * @param head 头节点
     * @param o1   任意一个子节点
     * @param o2   任意一个子节点
     * @return 最低公共祖先
     */
    public static Node lowestAncestor(Node head, Node o1, Node o2) {
        HashMap<Node, Node> fatherMap = new HashMap<>();
        fatherMap.put(head, head);

        process(head, fatherMap);

        // 记录第一个节点的所有祖先节点的无序集合
        HashSet<Node> set1 = new HashSet<>();

        set1.add(o1);

        Node cur = o1;
        // 只有头节点的父节点是自己，跳出条件：当前节点是头节点
        while (cur != fatherMap.get(cur)) {
            set1.add(cur);
            cur = fatherMap.get(cur);
        }
        // 头节点是所有节点的祖先
        set1.add(head);

        cur = o2;

        while (cur != fatherMap.get(cur)) {
            // 当前节点是不是最近公共祖先
            if (set1.contains(cur)) {
                // 是返回结束
                return cur;
            }

            // 让我的母节点去比较
            cur = fatherMap.get(cur);
        }

        // 前面没有最近共同祖先，则只可能是根节点
        return head;
    }

    /**
     * 递归记录所有节点的父节点信息
     *
     * @param head      头节点
     * @param fatherMap 记录的无序map
     */
    public static void process(Node head, HashMap<Node, Node> fatherMap) {
        if (head == null) {
            return;
        }

        fatherMap.put(head.left, head);
        fatherMap.put(head.right, head);

        process(head, fatherMap);
        process(head, fatherMap);
    }


    /**
     * 前提：两个节点属于 head为头的二叉树
     * 求一个二叉树的两个节点向上会聚的第一个点
     * <p>
     * 问题的情况：1. 对于o1 or o2其中有一个在另一个节点的子树中
     * 情况2：有另外一个节点是 最近祖先节点
     *
     * @param head 头节点
     * @param o1   任意一个子节点
     * @param o2   任意一个子节点
     * @return
     */
    public static Node lowestAncestor1(Node head, Node o1, Node o2) {
        // base case
        // 向下递归的过程中，碰到 o1 or o2, 就不会递归 这两个节点的子节点
        // 直接返回 o1 or o2
        if (head == null || head == o1 || head == o2) {
            return head;
        }

        Node left = lowestAncestor1(head.left, o1, o2);
        Node right = lowestAncestor1(head.right, o1, o2);

        // 对于o1 or o2其中有一个在另一个节点的子树中，这种情况不可能进入下面的if
        // o1 or o2 谁是祖先节点谁就必在 left or right 中
        // 故 left or right 一个不为空 一个为空
        if (left != null && right != null) {
            // 情况2：有另外一个节点是 最近祖先节点
            return head;
        }

        // 左右两颗树，并不都有返回值
        return left != null ? left : right;
    }
}
